1. Field of the Invention
This invention relates to a cell switching apparatus or cell switching system which switches a cell, in which various types of multi media information such as speech, data, image and so forth are transmitted, at a high speed.
2. Description of the Related Arts
Related Art 1.
In an Asynchronous Transfer Mode (ATM) communication system, consecutive signals such as a communication line signal and speech, and bursty signal such as data and motion video are all divided into a fixed length of signal. A header to indicate the destination information is then added to the fixed length of signal and thus a packet is composed. The information is transferred in the packet. A synchronization with a terminal and a network like a frame synchronization is not required and a speed at the terminal and the network is independent. Therefore, it is possible to handle ATM communications with any types of terminals. However, since packets arrive randomly at the high speed packet switch, a large number of packets may rush to one destination at a time. As a result, queueing of packets would be advantageous in order to prevent the loss of the information.
As to the problem, in FIGS. 5 and 6 in "PRELUDE: An Asynchronous Time-Division Switched Network", (Jean-Pierre Coudreuse, Michel Servel, session 22, article number 2, International Conference on Communications, 1987), an (n.times.m) shared buffer type high speed packet switch is proposed. This article relates to the high speed packet switch in the ATM communication system which effectively multiplexes and transmits line switching data and packet switching data. A conventional data queue unit is included in a controller 160. FIG. 29 is a block diagram showing the example.
Data arrive at n (n.gtoreq.2) number of incoming lines 1.sub.1 to 1.sub.n. The packet which reaches to the incoming lines has a fixed length. The data go out from m (m.gtoreq.2) number of outgoing lines 2.sub.1 to 2.sub.m. A packet multiplexing circuit 130 multiplexes the input packets. A shared buffer memory 140 can write the data in the indicated address and read out data with an indicated address without relating to the writing order by indicating the address. A packet demultiplexing circuit 150 demultiplexes read out packets. The controller 160 controls the packet switching.
Generally, memory operation speed is lower than gate operation speed. In this example, however, when the switch scale becomes large or the accommodated line speed becomes higher, the memory needs to operate faster.
Related Art 2.
FIG. 30 is a block diagram showing a conventional cell switching apparatus shown in Japanese Published and Unexamined Patent Hei 4-211548.
In FIG. 30, a cell is composed of a header and a payload part. The header includes its channel or path number as the destination information. Cells arrive at the n (n.gtoreq.2) number of incoming lines 1.sub.1 to 1.sub.n. The cells are transmitted to m (m.gtoreq.2) number of outgoing lines 2.sub.1 to 2.sub.m according to the destination information indicated by their headers.
Header processing circuits 10a.sub.1 to 10a.sub.n are provided to each of the incoming lines 1.sub.1 to 1.sub.n. The header processing circuits 10a.sub.1 to 10a.sub.n detect the outgoing lines 2.sub.1 to 2.sub.m as its destination according to the header of a cell arriving at the incoming lines 1.sub.1 to 1.sub.n.
Then, p (p.gtoreq.n) number of buffer memories 11.sub.1 to 11.sub.p store the cell in the indicated address. The stored cell can be read out from the buffer memories 11.sub.1 to 11.sub.p with an indicated address without relating to the writing order. A plurality of cells can be stored in the whole buffer memories 11.sub.1 to 11.sub.p.
Memory controllers 12.sub.1 to 12.sub.p are provided to each of the buffer memories 11.sub.1 to 11p. The memory controllers 12.sub.1 to 12.sub.p pool empty addresses by using the FIFO-type memory, for instance, and give the read addresses or write addresses to the corresponding buffer memories 11.sub.1 to 11.sub.p.
An incoming line space switch 13 selectively connects the header processing circuits 10a.sub.1 to 10a.sub.n to appropriate buffer memories 11.sub.1 to 11.sub.p. An outgoing line space switch 14 selectively connects the buffer memories 11.sub.1 to 11p to appropriate outgoing lines 2.sub.1 to 2.sub.m.
Outgoing line speed adjustment buffers 23.sub.1 to 23.sub.m are provided to each of the outgoing lines 2.sub.1 to 2.sub.m. The outgoing line speed adjustment buffers 23.sub.1 to 23.sub.m are connected to buffer memories 11.sub.1 to 11.sub.p via the outgoing line space switch 14. Then they store the cells that are read out at a r (2.gtoreq.r&lt;the number of outgoing lines) times of outgoing-line speed. The outgoing line speed adjustment buffers 23.sub.1 to 23.sub.m transmit the read out cells to the corresponding outgoing lines 2.sub.1 to 2.sub.m.
A buffer controller is has a writing buffer selective circuit 16, an address switching circuit 17, address queues 18.sub.1 to 18.sub.m and a read out buffer selective circuit 19. The buffer controller 15 controls the switching of the incoming line space switch 13 and selects buffers 11.sub.1 to 11p in which the cell is written. The buffer controller 15 then manages the addresses in the buffer memories 11.sub.1 to 11p in accordance with the destination information of the cell. Based on the results, the buffer controller 15 reads out the cells at r (2.gtoreq.r&lt;the number of outgoing lines) times of the outgoing speed in a fixed order. In addition, the outgoing line space switch 14 is controlled in order that the cells are transmitted to the outgoing lines 2.sub.1 to 2.sub.m indicated in their headers. The cells are then written in the associated outgoing line speed adjustment buffers 23.sub.1 to 23.sub.m. The cells are next read out at the outgoing-line speed to be transmitted to the associated outgoing lines 2.sub.1 to 2.sub.m.
In the buffer controller 15, when a cell reaches the incoming lines 1.sub.1 to 1.sub.n, the writing buffer selective circuit 16 receives the outgoing line number of the cell detected by the header processing circuits 10a.sub.1 to 10a.sub.n associated with the incoming lines 1.sub.1 to 1.sub.n. In order to select buffer memories 11.sub.1 to 11p for storing the cell and to connect the selected buffer memory to the header processing circuits 10a.sub.1 to 10a.sub.n, the writing buffer selective circuit 16 controls the switching of the incoming line space switch 13.
An address switching circuit 17 sorts the arriving cells with reference to the outgoing line numbers detected by the buffer selective circuit 16. The write addresses in the buffer memories 11.sub.1 to 11p in which the cells are written are received from the memory controllers 12.sub.1 to 12.sub.p associated with the buffer memories 11.sub.1 to 11.sub.p. Then, the write addresses are written into address queues which will be mentioned later.
The address queues 18.sub.1 to 18.sub.m are composed of the FIFO type memories and provided corresponding to each outgoing line 2.sub.1 to 2.sub.m. In the address queues 18.sub.1 to 18.sub.m, for each of associated outgoing lines 2.sub.1 to 2.sub.m, the write address on the buffer memories 11.sub.1 to 11p is written by the address switching circuit 17 in the arriving order. In the buffer memories 11.sub.1 to 11.sub.p, the cells whose destinations are the outgoing lines 2.sub.1 to 2.sub.n are stored.
The read out buffer selective circuit 19 chooses the cell to be read out from the buffer memories 11.sub.1 to 11p with reference to the address queues 18.sub.1 to 18.sub.m. The read out buffer selective circuit 19 reads out the addresses from the address queues 18.sub.1 to 18.sub.m, and sends them to the memory controllers 12.sub.1 to 12.sub.p which are associated with the buffer memories 11.sub.1 to 11.sub.p. Simultaneously, the read out buffer selective circuit 19 controls the switching of the outgoing line space switch 14 which connects the buffer memories 11.sub.1 to 11.sub.p to the associated outgoing lines 2.sub.1 to 2.sub.m.
The operation will now be described. FIGS. 31 to 33 are timing charts showing an example of each element. The chart shows a flow of control in a ease where the number of incoming lines 1.sub.1 to 1.sub.n, n is four and the number of outgoing lines 2.sub.1 to 2.sub.m, m is four as well and the number of buffer memories 11.sub.1 to 11p, p is 10.
The cell handled here has a fixed length and comes randomly. Before arriving at the incoming lines 1.sub.1 to 1.sub.n, cell input phase is adjusted, namely the cells arriving at all the lines have the same phase.
In FIGS. 31-33, (A) to (D) show one example of the cell input to the incoming lines 1.sub.1 to 1.sub.4. (E) to (N) show one example of the stored cells in the buffer memories 11.sub.1 to 11.sub.10. (O) to (R) show one example of cells to be transmitted from the outgoing lines 2.sub.1 to 2.sub.4. Herein, is assumed that all the circuits are synchronized and the input and output of one cell can be done in one time slot.
When cells come to the incoming lines 1.sub.1 to 1.sub.4, the header processing circuits 10a.sub.1 to 10a.sub.4 which are associated with each incoming lines 1.sub.1 to 1.sub.4 detect the outgoing line number from the headers of the incoming cells. The writing buffer selective circuit 16 in the buffer controller 15 directs the incoming line space switch 13 to connect the incoming lines 1.sub.1 to 1.sub.4 where the cell arrived to the buffer memories 11.sub.1 to 11.sub.10 which are selected to store the cells, respectively, with reference to the header processing circuits 10a.sub.1 to 10a.sub.4.
Various types connecting methods of the incoming line space switch 13 are possible. When some cells are stored in the buffer memories 11.sub.1 to 11.sub.10 and read out later, it is not desirable that there are two or more cells to be read out from the same buffer memory. Therefore, the method of distributing the cells to a lot of buffer memories 11.sub.1 to 11.sub.10 is most applicable.
In this case, the number of the buffer memories is insufficient when it equals to the number of the incoming lines 1.sub.1 to 1.sub.4. In order to solve the foregoing problems, having as many buffer memories as possible can simplify the control.
Here we propose a further simplified control example where the buffer memory with the minimum cell storage is selected and incoming cells are written there. In this method, when the x number of cells arrive simultaneously, the x number of buffer memories which have the least cell storage are selected and the incoming lines 1.sub.1 to 1.sub.4 are connected to the selected buffer memories.
Here is another simplified example of control in which buffer memories 11.sub.1 to 11.sub.10 are selected in order, and the arriving cells are being written. Namely, the buffer memories 11.sub.1, 11.sub.2, 11.sub.3 . . . 11.sub.10 are selected in regular order and the arriving cells are being written.
In time slot 1 as shown in FIG. 31, F1 cell, the first cell of a signal f (Hereinafter, the first cell of the signal f is referred to as F1 cell. Other cells which will be described are referred to in the same way.), is received from the incoming line 1.sub.1. G1 cell of a signal g is received from the incoming line 1.sub.2 and an I1 cell of a signal i is input from the incoming line 1.sub.4. The header part of each cell has an outgoing line number of the destination. i.e., F1 cell has O.sub.1 to indicate the outgoing line 2.sub.1, G1 cell has O.sub.4 to indicate the outgoing line 2.sub.4 and I1 cell has O.sub.3 to indicate the outgoing line 2.sub.3.
In time slot 2, the incoming line space switch 13 connects the incoming line 1.sub.1 to the buffer memory 11.sub.1, the incoming line 1.sub.2 to the buffer memory 11.sub.2, and the incoming line 1.sub.4 to the buffer memory 11.sub.3, respectively. Accordingly, in the time slot 2, these cells are stored at the address indicated by the memory controllers 12.sub.1 to 12.sub.3 in the buffer memories 11.sub.1 to 11.sub.3.
From each of the memory controllers 12.sub.1 to 12.sub.p, the write address of each of the buffer memories 11.sub.1 to 11.sub.3 are transmitted to the address switching circuit 17. The write address is selected among the addresses which the memory controllers 12.sub.1 to 12.sub.3 manage as empty addresses.
The address switching circuit 17 sorts each incoming cell according to the destination output lines with reference to the writing buffer selective circuit 16. The address switching circuit 17 then writes the write address of the buffer memory 11.sub.1 on the address queue 18.sub.1, the write address of the buffer memory 11.sub.2 on the address queue 18.sub.4 and the write address of the buffer memory 11.sub.3 at the tail of the address queue 18.sub.3, respectively.
In time slot 3, the read out buffer selective circuit 19 extracts the address stored in the address queues 18.sub.1 to 18.sub.4 and sends it to the memory controllers 12.sub.1 to 12.sub.3 associated with the buffer memories 11.sub.1 to 11.sub.3. Meanwhile, the read out buffer selective circuit 19 directs the outgoing space switch 14 to connect the buffer memories 11.sub.1 to 11.sub.3 to the outgoing lines 2.sub.1, 2.sub.3 and 2.sub.4, respectively. Hereby, in the time slot 3, the outgoing space switch 14 connects the buffer memory 11.sub.1 to the outgoing line 2.sub.1, the buffer memory 11.sub.2 to the outgoing line 2.sub.4, the buffer memory 11.sub.3 to the outgoing line 2.sub.3, respectively.
Each of the memory controllers 12.sub.1 to 12.sub.3 transmits the received address to the associated buffer memories 11.sub.1 to 11.sub.3 as the read address. After that, the address is managed as an empty address. The cell read out from each of the buffer memories 11.sub.1 to 11.sub.3 are output to the destinations indicated by each header, i.e., the outgoing lines 2.sub.1, 2.sub.4, and 2.sub.3.
In the above-stated examples, the destination outgoing lines of the input cell were all different. The cells input in the time slot 2 however have the identical destination outgoing line. An F2 cell, a G2 cell and an H1 cell input in the time slot 2 are written on the buffer memories 11.sub.4, 11.sub.5, and 11.sub.6, respectively. Each of the headers of these three cells has O.sub.4 to indicate the outgoing line 2.sub.4.
In an example in FIGS. 31 to 33, the output priority of the outgoing cells is given in numerical order of the incoming line number and the queuing of the cell is carried out according to the priority. In time slots 4, 5, and 6, the F2, the G2, and the H1 cells are read out in the order of the buffer memories 11.sub.4, 11.sub.5, 11.sub.6 and transferred to the outgoing lines 3.sub.4 based on the output priority. Hereinafter, the switching of the cell is executed according to this procedure.
In time slot 8, an I2 cell and an H6 cell are stored in the buffer memory 11.sub.3. As for these cells, each destination is different from each other. For instance, in case of the I2 cell, the destination is the outgoing line 2.sub.2 and in case of the H6 cell, the outgoing line 2.sub.3. If they are read out at the same speed of the outgoing line speed of the outgoing lines 2.sub.1 to 2.sub.4, they cannot be extracted simultaneously because both of them are stored in a single buffer memory, i.e., the buffer memory 11.sub.3.
FIGS. 34 to 35 are timing charts showing extended parts of time slots 6 to 13 in FIGS. 31 to 33. In FIGS. 34 to 35, there is shown a case that the read out of the buffer memories 11.sub.1 to 11.sub.10 is performed at a three times of outgoing line speed. In the figure, (E) to (N) show an example of stored cells, (S) to (V) show a writing state of the cell to the outgoing line speed adjustment buffers 23.sub.1 to 23.sub.4. (O) to (R) show an example of cell output from the outgoing lines 2.sub.1 to 2.sub.4.
In the above-stated time slot 8, each of the I2 cell and the H6 cell in the buffer memory 11.sub.3 has its own destination. When they are read out at a three times of outgoing line speed by the buffer memory 11.sub.3, it is possible to transfer both of the cells to the associated outgoing lines 2.sub.2 and 2.sub.3 simultaneously. Namely, when they are read out at a three times of outgoing line speed from the buffer memories 11.sub.1 to 11.sub.10, up to three cells can be read out from each of the buffer memories 11.sub.1 to 11.sub.10 in the same time slot.
Such eases occur in other time slots 9, 10 and 15. In any case, waiting of cells is not happening even though the plurality of cells are in the same queue and the output cell collision can be prevented.
Here, there was shown a case that the read out speed of the buffer memories 11.sub.1 to 11.sub.10 is assumed to be three times of the outgoing line speed. In general, the read out speed can be r times of the outgoing line speed, which is more than two times and less than the number of outgoing lines. As each of the buffer memories 11.sub.1 to 11.sub.10, a dual-port memory can be used. However, a single-port memory operable at more than a double speed is also useful.
In a case where the number of cells to be read out from the same buffer memory, in one time slot exceeds the number r, it is possible to avoid all the collision when only the r number of cells are extracted by giving the priority corresponding to the outgoing lines 2.sub.1 to 2.sub.m. The priority should be updated at each time according to a predefined method or randomly. In this way, waiting of cells is not happening even though the plurality of cells are in the same queue and the output cell collision can be prevented.
Related Art 3.
Another related art will now be described with reference to attached figures. FIG. 36 is a block diagram showing a configuration of a conventional cell switching apparatus. The same signs are attached to the elements equivalent or corresponding to those of the cell switching apparatus according to the related art 2 and the explanation will be omitted.
In FIG. 36, incoming-line speed-adjustment buffers 24.sub.1 to 24.sub.n are provided associated with each of the incoming lines 1.sub.1 to 1.sub.n. The cell transmitted from the associated header processing circuits 10a.sub.1 to 10a.sub.n is stored in incoming-line speed-adjustment buffers 24.sub.1 to 24.sub.n. The cell is then read out at a speed of w (2.gtoreq.w&lt;the number of incoming lines) times of incoming line speed and transmitted to appropriate buffers 11.sub.1 to 11p connected by the incoming line space switch 13.
The buffer controller 15 has the writing buffer selective circuit 16, the address switching circuit 17, the address queues 18.sub.1 to 18.sub.m, and the read out buffer selective circuit 19. The cell stored in the incoming-line speed-adjustment buffers 24.sub.1 to 24.sub.n is read out at a speed of w (2.gtoreq.w&lt;the number of incoming lines) times of incoming line speed. By selecting the buffer memories 11.sub.1 to 11p to which the cell is written by controlling the incoming line space switch 13, the cell is written in the buffer memories 11.sub.1 to 11p at a speed of w times of the incoming line speed. Simultaneously, the address of the buffer memories 11.sub.1 to 11p is managed according to destinations of the cells. The buffer controller 15 controls the outgoing line space switch 14 and transmits the cell to the outgoing lines 2.sub.1 to 2.sub.m indicated at the header of the cell in an appropriate order.
The operation will now be described. FIGS. 37 to 38 are timing charts showing the timing point of the signals of each element. As in the Related Art 2, there is shown a flow of control in a case where the number of incoming lines 1.sub.1 to 1.sub.n, n and the number of outgoing lines 2.sub.1 to 2.sub.m, m are four, respectively and the number of the buffer memories 11.sub.1 to 11.sub.p, p is ten. The (A) to (R) are equivalent to those in FIGS. 31 to 33, respectively.
The capacity of each of the buffer memories 11.sub.1 to 11p is two cells. The cell treated here arrives at random in a fixed length. Before coming to the incoming lines 1.sub.1 to 1.sub.n, the cell input phase is adjusted and the cell arriving at all the lines is assumed to be supplied with the same phase.
When the cell comes to the incoming lines 1.sub.1 to 1.sub.4, the header processing circuits 10.sub.1 to 10.sub.4 associated with each of the incoming lines 1.sub.1 to 1.sub.4 detect the outgoing line number from the header and writes the cell in the associated incoming-line speed-adjustment buffers 24.sub.1 to 24.sub.4.
On the other hand, the writing buffer selective circuit 16 in the buffer controller 15 directs the incoming line space switch 18 to connect the incoming line speed adjustment buffers 24.sub.1 to 24.sub.4 with the buffer memories 11.sub.1 to 11.sub.10 selected to store the cell.
The read out speed of the incoming-line speed-adjustment buffers 24.sub.1 to 24.sub.4, i.e., the writing speed of the buffer memories 11.sub.1 to 11.sub.10 are assumed to be twice of the incoming line speed of the incoming lines 1.sub.1 to 1.sub.4. In one time slot, two cells can be written in the same buffer memory.
It is assumed that buffer memories 11.sub.1, 11.sub.2, . . . 11.sub.3, . . . 11.sub.10 are selected in this order and the arrived cells are being consecutively written. When there is a buffer memory which is already full among the buffer memories 11.sub.1 to 11.sub.10 in one time slot, the buffer memory is ignored and the cell is written in the next buffer memory.
It is desirable to distribute the writing of the cells in the different buffer memories 11.sub.1 to 11.sub.10. In this example, the write speed of the buffer memories 11.sub.1 to 11.sub.10 is set to be twice of the incoming speed. Accordingly, in a case where there occurs a cell discard in one buffer memories 11.sub.1 to 11.sub.10, the writing of plural cells (two cells) in one time slot is allowed so as to lower the chance of cell discard.
Namely, an F10 cell, an H10 cell, and an I8 cell are arriving in time slot 11 in FIGS. 37 to 39. Only two cells in the empty buffer memory 11.sub.6 in time slot 11 and one cell of the empty buffer memory 11.sub.7 are available at this time. Therefore, it is impossible to write each of them at different buffer memories.
Accordingly, by using the fact that the writing speed to the buffer memories 11.sub.1 to 11.sub.10 is twice of the incoming line speed, the cell discard is prevented by writing two cells, the F10 cell and the H10 cell in the buffer memory 11.sub.6. There is shown a state that the writing of these three cells is finished in (J), (K) of FIG. 38 surrounded by the actual line.
Hereinafter, the basic procedure of cell switching is performed as in the Related Art 2.
As has been described, there is shown a case that the write speed to the buffer memories 11.sub.1 to 11.sub.10 is assumed to be twice of the incoming line speed. In general, the incoming line speed can be w times. W is more than two and less than the number of incoming lines. For each of the buffer memories 11.sub.1 to 11.sub.10, a dual-port memory can be used. However, a single-port memory operable more than a double speed is also useful.
As described in Related Art 1, in the shared buffer type switch of (n.times.m) size, when n or m becomes large, the size of the shared buffer memory (SBM) enlarges according to the number of the outgoing lines m. In addition, since the number of the accesses is proportional to (n+m), the SBM should adopt a high speed memory.
If a switch which has only one conventional SBM, so as to realize the scale of (n.times.m), the SBM needs the higher access speed in proportion to (n+m). Consequently, when the number of incoming lines n increases, the operation speed of the memory will be the problem.
In the switch which provides a plurality of buffer memories as shown in Related Arts 2 and 3, the problem that the memory to implement the high speed access should be adopted will be eased, compared with the switch which has only one shared buffer memory as shown in Related Art 1.
In Related Art 2, there is shown a case in which the switching function will be further improved by increasing the read-out speed. As in Related Art 3, there is shown a case of improving the switching ability by increasing the writing speed. In Related Arts 2 and 3, it was mentioned that the processing ability of the switch will be improved by increasing the read-out and write speed of the cell. However, there were less description about how the read out and write of the cell is concretely performed with high speed.